package leetcode_1100;

import helpclass.TreeNode;

/**
 *@author 周杨
 *ConstructBinarySearchTreeFromPreorderTraversal_1008 给一棵二叉树的先序遍历 将其重构成一颗平衡二叉树 保证是合法的
 *describe:递归即可 AC 100%
 *2019年3月23日 下午13:47
 */
public class ConstructBinarySearchTreeFromPreorderTraversal_1008 {
	public TreeNode bstFromPreorder(int[] preorder) {
        return help(preorder,0,preorder.length-1);
    }
	public TreeNode help(int[]preorder,int left,int right) {
		if (left > right) return null;
		if (left == right) return new TreeNode(preorder[left]);
		TreeNode root = new TreeNode(preorder[left]);
		int mid = left+1;
		while(mid <= right) 
			if(preorder[mid] < root.val) ++mid;
			else break;
		root.left = help(preorder,left+1,mid-1);
		root.right = help(preorder,mid,right);
		return root;
	}
}
